#leetcode题目121：买卖股票的最佳时机
#题目分析：只能买卖一次，所以只需要找到最低点买入，最高点卖出即可。

#难度：简单
#时间复杂度：O(n)


#贪心算法

from typing import List
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """
        买卖股票的最佳时机
        给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
        你只能选择某一天买入这只股票，并选择在未来的某一天卖出该股票。
        返回你可以从这笔交易中获取的最大利润。
        """
        n = len(prices)
        res = 0 #要返回的利润
        h = float('-inf') #初始化最高价格为负无穷，因为后续要更新最高价格，只要比对这个一定会比这个高
        # 记录从右往左遍历时的最高价格
        
        # 从右往左遍历，让我们能够"预知未来"，知道从当前位置往右的最高价格，从而正确计算如果在这里买入能获得的最大利润。
        for i in range(n - 1, -1, -1):#这里的i是从右往左遍历的，所以是n - 1, -1, -1
            if prices[i] > h: 
                h = prices[i] #h表示记录在出手价格上，可能的最高价格
            res = max(res, h - prices[i])#交易差值是最大的则为最优答案，出手价格（右侧）-买入价格（左侧），所以为什么是倒序的原因
        
        return res



#测试数据
prices = [7,1,5,3,6,4]
#预期输出：5
solution = Solution()
print(solution.maxProfit(prices))

prices = [7,6,4,3,1]
#预期输出：0
solution = Solution()
print(solution.maxProfit(prices))
